package partitionproblem;

public class UserMainCode {
	private static int sum(int[] S) {
		int sum = 0;
		for(int s : S)
			sum += s;
		return sum;
	}
	private static String partition(int[] S) {
		int n = S.length;
		for(int i = 0; i < n; i++)
			if(S[i] <= 0)
				return "Invalid";
		int N = sum(S);
		if(N % 2 != 0)
			return "No";
		boolean P[][] = new boolean[N / 2 + 1][n + 1];
		for(int c = 0; c <= n; c++)
			P[0][c] = true;
		for(int r = 1; r <= N / 2; r++)
			P[r][0] = false;
		for(int i = 1; i <= N / 2; i++)
			for(int j = 1; j <= n; j++)
				P[i][j] = P[i][j - 1] || i >= S[j - 1] && P[i - S[j - 1]][j - 1];
		return P[N / 2][n] ? "Yes" : "No";
	}
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		int[] S1 = {1,5,11,5};
		System.out.println(partition(S1));
		int[] S2 = {1,5,3};
		System.out.println(partition(S2));
		int[] S3 = {};
		System.out.println(partition(S3));
		int[] S4 = {5,9};
		System.out.println(partition(S4));
		int[] S5 = {5,-9};
		System.out.println(partition(S5));
	}
}
